package main

import "fmt"

// 如何展开链接列表

func main() {
	head := createNode()
	flatten(head)
	printNode("扁平化链表后：", head)
}

func flatten(root *lNode) {
	if root == nil || root.right == nil {
		return
	}

	flatten(root.right)
	merge(root, root.right)
	return
}

func merge(a *lNode, b *lNode) *lNode {
	if a == nil {
		return b
	}

	if b == nil {
		return a
	}

	var result *lNode
	if a.data < b.data {
		result = a
		result.down = merge(a.down, b)
	} else {
		result = b
		result.down = merge(a, b.down)
	}

	return result
}

type lNode struct {
	data  int
	right *lNode
	down  *lNode
}

func (p *lNode) insert(headRef *lNode, data int) *lNode {
	return &lNode{
		data: data,
		down: headRef,
	}
}

func createNode() *lNode {
	node := &lNode{}

	node = node.insert(nil, 31)
	node = node.insert(node, 8)
	node = node.insert(node, 6)
	node = node.insert(node, 3)

	node.right = node.insert(node.right, 21)
	node.right = node.insert(node.right, 11)

	return node
}

func printNode(info string, node *lNode) {
	fmt.Println(info)

	current := node
	for current != nil {
		fmt.Print(current.data, " ")
		current = current.down
	}
}
